package com.coding.basic.stack.expr;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InfixToPostfix {

    public static List<Token> convert(String expr) {
        TokenParser parser = new TokenParser();
        List<Token> tokenList = parser.parse(expr);

        List<Token> convert = new ArrayList<>();
        Stack<Token> opStack = new Stack<>();
        for (int i = 0; i < tokenList.size(); i++) {
            Token token = tokenList.get(i);

            if (token.isNumber()) {
                convert.add(token);
            } else if (token.isOperator()) {
                if (opStack.isEmpty()) {
                    opStack.push(token);
                } else {
                    Token preOperator = opStack.peek();
                    if (token.hasHigherPriority(preOperator)) {
                        Token nextNum = tokenList.get(++i);

                        convert.add(nextNum);
                        convert.add(token);
                    } else {
                        convert.add(preOperator);

                        opStack.pop();
                        opStack.push(token);
                    }
                }
            }
        }

        if (!opStack.isEmpty()) {
            Token operator = opStack.pop();
            convert.add(operator);
        }
        return convert;
    }
}